How do I get to Cassima?

Hint 1 of 4:

You won't be able to talk to her for a long while.

Hint 2 of 4:

But you can at least try to get into the castle to find out where she is.

Hint 3 of 4:

The guard dogs will only let you through if you can prove you're royalty.
Look around the beach for proof.